/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// dfs，递归：根节点+左右子树路径
// time: O(n), space: O(logn)，递归栈深度
func pathSum(root *TreeNode, targetSum int) [][]int {
	return re(root, targetSum)
}

func re(root *TreeNode, targetSum int) [][]int {
	// 递归退出条件
	if root == nil {
		return nil
	}

	if root.Val == targetSum && root.Left == nil && root.Right == nil {
		return [][]int{{root.Val}}
	}

	var res [][]int
	leftRes := re(root.Left, targetSum-root.Val)
	if leftRes != nil {
		for _, arr := range leftRes {
			tmp := []int{root.Val}
			if arr != nil {
				tmp = append(tmp, arr...)
				res = append(res, tmp)
			}
		}
	}
	rightRes := re(root.Right, targetSum-root.Val)
	if rightRes != nil {
		for _, arr := range rightRes {
			tmp := []int{root.Val}
			if arr != nil {
				tmp = append(tmp, arr...)
				res = append(res, tmp)
			}
		}
	}
	return res
}